from functools import lru_cache


class Solution:
    def canPartition(self, nums) -> bool:
        all = sum(nums)
        if all & 1 == 1:
            return False
        if len(nums) == 1:
            return False
        half = all // 2
        nums.sort()

        @lru_cache(None)
        def startSum(start, target):
            if len(nums) <= start:
                return False
            if target == nums[start]:
                return True
            if target < nums[start]:
                return False
            return startSum(start + 1, target) or startSum(start + 1, target - nums[start])

        return startSum(0, half)


if __name__ == '__main__':
    so = Solution()
    num = [1, 5, 11, 5]
    r = so.canPartition(num)
    print(r)
